//
// Description: 392. 判断子序列
// Created by Loading on 2022/7/10.
//

#include <bits/stdc++.h>

using namespace std;

bool isSubsequence(string s, string t) {
    int n = s.size();
    int m = t.size();

    // dp[i][j] 表示 t 中，从位置 i 开始，j 字符第一次出现的位置
    vector<vector<int>> dp(m + 1, vector<int>(26));
    for (int i = 0; i < 26; ++i) {
        dp[m][i] = m;
    }

    // 需要逆序遍历
    for (int i = m - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) {
            if (t[i] == 'a' + j) {
                dp[i][j] = i;
            } else {
                dp[i][j] = dp[i + 1][j];
            }
        }
    }

    // 每次只查找 index 位置后的第一个 s[i] 的位置，若存在，则从该位置的下一个位置继续匹配下一个字符
    for (int i = 0, index = 0; i < n; index = dp[index][s[i] - 'a'] + 1, ++i) {
        // 表示 t 在 index 位置的后面再也没有 s[i] 了，匹配失败
        if (dp[index][s[i] - 'a'] == m) {
            return false;
        }
    }

    return true;
}

int main() {
    string s = "abc", t = "ahbgdc";

    auto res = isSubsequence(s, t);

    cout << res << endl;

    return 0;
}
